Skip to content

Latest commit

 

History

History
113 lines (97 loc) · 3.31 KB

README.md

File metadata and controls

113 lines (97 loc) · 3.31 KB

599. Minimum Index Sum of Two Lists

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

Example 1:

Input: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] Output: ["Shogun"] Explanation: The only restaurant they both like is "Shogun".

Example 2:

Input: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["KFC", "Shogun", "Burger King"] Output: ["Shogun"] Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).

Note:

  1. The length of both lists will be in the range of [1, 1000].
  2. The length of strings in both lists will be in the range of [1, 30].
  3. The index is starting from 0 to the list length minus 1.
  4. No duplicates in both lists.

Solutions (Rust)

1. Brute Force

implSolution{pubfnfind_restaurant(list1:Vec<String>,list2:Vec<String>) -> Vec<String>{letmut min_sum = std::usize::MAX;letmut ret = Vec::new();for i in0..list1.len(){for j in0..list2.len(){if list1[i] == list2[j]{if i + j == min_sum { ret.push(list2[j].to_string());}elseif i + j < min_sum { ret.clear(); ret.push(list2[j].to_string()); min_sum = i + j;}break;}}} ret }}

2. HashMap

use std::collections::HashMap;implSolution{pubfnfind_restaurant(list1:Vec<String>,list2:Vec<String>) -> Vec<String>{letmut rest_idx = list1 .iter().enumerate().map(|(i, s)| (s, i)).collect::<HashMap<&String,usize>>();letmut min_sum = std::usize::MAX;letmut ret = Vec::new();for i in0..list2.len(){ifletSome(j) = rest_idx.get(&list2[i]){if i + j == min_sum { ret.push(list2[i].to_string());}elseif i + j < min_sum { ret.clear(); ret.push(list2[i].to_string()); min_sum = i + j;}}} ret }}

3. Increasing Sum

implSolution{pubfnfind_restaurant(list1:Vec<String>,list2:Vec<String>) -> Vec<String>{letmut flag = false;letmut ret = Vec::new();for sum in0..(list1.len() + list2.len() - 1){for i in(sum + 1).saturating_sub(list2.len())..(sum + 1).min(list1.len()){if list1[i] == list2[sum - i]{ flag = true; ret.push(list1[i].to_string());}}if flag {break;}} ret }}
close